/**
 * All rights Reserved, Designed By 溪云阁
 * Copyright:    Copyright(C) 2016-2020
 */

package com.algorithm;

import java.util.Arrays;

/**
 * 快速排序算法
 * @author：溪云阁
 * @date：2020年5月3日
 */

public class QuickAlgorithm {

    /**
     * 快速排序
     * @author 溪云阁
     * @param arr        待排序列
     * @param leftIndex  待排序列起始位置
     * @param rightIndex 待排序列结束位置
     */
    public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        } else {
            int left = leftIndex;
            int right = rightIndex;
            // 待排序的第一个元素作为基准值
            final int key = arr[left];
            // 从左右两边交替扫描，直到left = right
            while (left < right) {
                while (right > left && arr[right] >= key) {
                    // 从右往左扫描，找到第一个比基准值小的元素
                    right--;
                }
                // 找到这种元素将arr[right]放入arr[left]中
                arr[left] = arr[right];
                while (left < right && arr[left] <= key) {
                    // 从左往右扫描，找到第一个比基准值大的元素
                    left++;
                }
                // 找到这种元素将arr[left]放入arr[right]中
                arr[right] = arr[left];
            }
            // 基准值归位
            arr[left] = key;
            // 对基准值左边的元素进行递归排序
            quickSort(arr, leftIndex, left - 1);
            // 对基准值右边的元素进行递归排序。
            quickSort(arr, right + 1, rightIndex);
        }
    }

    public static void main(String[] args) {
        final int[] arr = { 2, 3, 5, 1, 23, 6, 78, 34, 23, 4, 5, 78, 34, 65, 32, 65, 76, 32, 76, 9 };
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }

}
